//
// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
//
// This software is provided 'as-is', without any express or implied
// warranty.  In no event will the authors be held liable for any damages
// arising from the use of this software.
// Permission is granted to anyone to use this software for any purpose,
// including commercial applications, and to alter it and redistribute it
// freely, subject to the following restrictions:
// 1. The origin of this software must not be misrepresented; you must not
//    claim that you wrote the original software. If you use this software
//    in a product, an acknowledgment in the product documentation would be
//    appreciated but is not required.
// 2. Altered source versions must be plainly marked as such, and must not be
//    misrepresented as being the original software.
// 3. This notice may not be removed or altered from any source distribution.
//

#ifndef DETOURNAVMESHQUERY_H
#define DETOURNAVMESHQUERY_H

#include "DetourNavMesh.h"
#include "DetourStatus.h"


// Define DT_VIRTUAL_QUERYFILTER if you wish to derive a custom filter from dtQueryFilter.
// On certain platforms indirect or virtual function call is expensive. The default
// setting is to use non-virtual functions, the actual implementations of the functions
// are declared as inline for maximum speed. 

//#define DT_VIRTUAL_QUERYFILTER 1

/// Defines polygon filtering and traversal costs for navigation mesh query operations.
/// @ingroup detour
class dtQueryFilter
{
    float m_areaCost[DT_MAX_AREAS];        ///< Cost per area type. (Used by default implementation.)
    unsigned short m_includeFlags;        ///< Flags for polygons that can be visited. (Used by default implementation.)
    unsigned short m_excludeFlags;        ///< Flags for polygons that should not be visted. (Used by default implementation.)
    
public:
    dtQueryFilter();
    
#ifdef DT_VIRTUAL_QUERYFILTER
    virtual ~dtQueryFilter() { }
#endif
    
    /// Returns true if the polygon can be visited.  (I.e. Is traversable.)
    ///  @param[in]        ref        The reference id of the polygon test.
    ///  @param[in]        tile    The tile containing the polygon.
    ///  @param[in]        poly  The polygon to test.
#ifdef DT_VIRTUAL_QUERYFILTER
    virtual bool passFilter(const dtPolyRef ref,
                            const dtMeshTile* tile,
                            const dtPoly* poly) const;
#else
    bool passFilter(const dtPolyRef ref,
                    const dtMeshTile* tile,
                    const dtPoly* poly) const;
#endif

    /// Returns cost to move from the beginning to the end of a line segment
    /// that is fully contained within a polygon.
    ///  @param[in]        pa            The start position on the edge of the previous and current polygon. [(x, y, z)]
    ///  @param[in]        pb            The end position on the edge of the current and next polygon. [(x, y, z)]
    ///  @param[in]        prevRef        The reference id of the previous polygon. [opt]
    ///  @param[in]        prevTile    The tile containing the previous polygon. [opt]
    ///  @param[in]        prevPoly    The previous polygon. [opt]
    ///  @param[in]        curRef        The reference id of the current polygon.
    ///  @param[in]        curTile        The tile containing the current polygon.
    ///  @param[in]        curPoly        The current polygon.
    ///  @param[in]        nextRef        The refernece id of the next polygon. [opt]
    ///  @param[in]        nextTile    The tile containing the next polygon. [opt]
    ///  @param[in]        nextPoly    The next polygon. [opt]
#ifdef DT_VIRTUAL_QUERYFILTER
    virtual float getCost(const float* pa, const float* pb,
                          const dtPolyRef prevRef, const dtMeshTile* prevTile, const dtPoly* prevPoly,
                          const dtPolyRef curRef, const dtMeshTile* curTile, const dtPoly* curPoly,
                          const dtPolyRef nextRef, const dtMeshTile* nextTile, const dtPoly* nextPoly) const;
#else
    float getCost(const float* pa, const float* pb,
                  const dtPolyRef prevRef, const dtMeshTile* prevTile, const dtPoly* prevPoly,
                  const dtPolyRef curRef, const dtMeshTile* curTile, const dtPoly* curPoly,
                  const dtPolyRef nextRef, const dtMeshTile* nextTile, const dtPoly* nextPoly) const;
#endif

    /// @name Getters and setters for the default implementation data.
    ///@{

    /// Returns the traversal cost of the area.
    ///  @param[in]        i        The id of the area.
    /// @returns The traversal cost of the area.
    inline float getAreaCost(const int i) const { return m_areaCost[i]; }

    /// Sets the traversal cost of the area.
    ///  @param[in]        i        The id of the area.
    ///  @param[in]        cost    The new cost of traversing the area.
    inline void setAreaCost(const int i, const float cost) { m_areaCost[i] = cost; } 

    /// Returns the include flags for the filter.
    /// Any polygons that include one or more of these flags will be
    /// included in the operation.
    inline unsigned short getIncludeFlags() const { return m_includeFlags; }

    /// Sets the include flags for the filter.
    /// @param[in]        flags    The new flags.
    inline void setIncludeFlags(const unsigned short flags) { m_includeFlags = flags; }

    /// Returns the exclude flags for the filter.
    /// Any polygons that include one ore more of these flags will be
    /// excluded from the operation.
    inline unsigned short getExcludeFlags() const { return m_excludeFlags; }

    /// Sets the exclude flags for the filter.
    /// @param[in]        flags        The new flags.
    inline void setExcludeFlags(const unsigned short flags) { m_excludeFlags = flags; }    

    ///@}

};



/// Provides information about raycast hit
/// filled by dtNavMeshQuery::raycast
/// @ingroup detour
struct dtRaycastHit
{
    /// The hit parameter. (FLT_MAX if no wall hit.)
    float t; 
    
    /// hitNormal    The normal of the nearest wall hit. [(x, y, z)]
    float hitNormal[3];
    
    /// Pointer to an array of reference ids of the visited polygons. [opt]
    dtPolyRef* path;
    
    /// The number of visited polygons. [opt]
    int pathCount;

    /// The maximum number of polygons the @p path array can hold.
    int maxPath;

    ///  The cost of the path until hit.
    float pathCost;
};



/// Provides the ability to perform pathfinding related queries against
/// a navigation mesh.
/// @ingroup detour
class dtNavMeshQuery
{
public:
    dtNavMeshQuery();
    ~dtNavMeshQuery();
    
    /// Initializes the query object.
    ///  @param[in]        nav            Pointer to the dtNavMesh object to use for all queries.
    ///  @param[in]        maxNodes    Maximum number of search nodes. [Limits: 0 < value <= 65536]
    /// @returns The status flags for the query.
    dtStatus init(const dtNavMesh* nav, const int maxNodes);
    
    /// @name Standard Pathfinding Functions
    // /@{

    /// Finds a path from the start polygon to the end polygon.
    ///  @param[in]        startRef    The refrence id of the start polygon.
    ///  @param[in]        endRef        The reference id of the end polygon.
    ///  @param[in]        startPos    A position within the start polygon. [(x, y, z)]
    ///  @param[in]        endPos        A position within the end polygon. [(x, y, z)]
    ///  @param[in]        filter        The polygon filter to apply to the query.
    ///  @param[out]    path        An ordered list of polygon references representing the path. (Start to end.) 
    ///                              [(polyRef) * @p pathCount]
    ///  @param[out]    pathCount    The number of polygons returned in the @p path array.
    ///  @param[in]        maxPath        The maximum number of polygons the @p path array can hold. [Limit: >= 1]
    dtStatus findPath(dtPolyRef startRef, dtPolyRef endRef,
                      const float* startPos, const float* endPos,
                      const dtQueryFilter* filter,
                      dtPolyRef* path, int* pathCount, const int maxPath) const;
    
    /// Finds the straight path from the start to the end position within the polygon corridor.
    ///  @param[in]        startPos            Path start position. [(x, y, z)]
    ///  @param[in]        endPos                Path end position. [(x, y, z)]
    ///  @param[in]        path                An array of polygon references that represent the path corridor.
    ///  @param[in]        pathSize            The number of polygons in the @p path array.
    ///  @param[out]    straightPath        Points describing the straight path. [(x, y, z) * @p straightPathCount].
    ///  @param[out]    straightPathFlags    Flags describing each point. (See: #dtStraightPathFlags) [opt]
    ///  @param[out]    straightPathRefs    The reference id of the polygon that is being entered at each point. [opt]
    ///  @param[out]    straightPathCount    The number of points in the straight path.
    ///  @param[in]        maxStraightPath        The maximum number of points the straight path arrays can hold.  [Limit: > 0]
    ///  @param[in]        options                Query options. (see: #dtStraightPathOptions)
    /// @returns The status flags for the query.
    dtStatus findStraightPath(const float* startPos, const float* endPos,
                              const dtPolyRef* path, const int pathSize,
                              float* straightPath, unsigned char* straightPathFlags, dtPolyRef* straightPathRefs,
                              int* straightPathCount, const int maxStraightPath, const int options = 0) const;

    ///@}
    /// @name Sliced Pathfinding Functions
    /// Common use case:
    ///    -# Call initSlicedFindPath() to initialize the sliced path query.
    ///    -# Call updateSlicedFindPath() until it returns complete.
    ///    -# Call finalizeSlicedFindPath() to get the path.
    ///@{ 

    /// Intializes a sliced path query.
    ///  @param[in]        startRef    The refrence id of the start polygon.
    ///  @param[in]        endRef        The reference id of the end polygon.
    ///  @param[in]        startPos    A position within the start polygon. [(x, y, z)]
    ///  @param[in]        endPos        A position within the end polygon. [(x, y, z)]
    ///  @param[in]        filter        The polygon filter to apply to the query.
    ///  @param[in]        options        query options (see: #dtFindPathOptions)
    /// @returns The status flags for the query.
    dtStatus initSlicedFindPath(dtPolyRef startRef, dtPolyRef endRef,
                                const float* startPos, const float* endPos,
                                const dtQueryFilter* filter, const unsigned int options = 0);

    /// Updates an in-progress sliced path query.
    ///  @param[in]        maxIter        The maximum number of iterations to perform.
    ///  @param[out]    doneIters    The actual number of iterations completed. [opt]
    /// @returns The status flags for the query.
    dtStatus updateSlicedFindPath(const int maxIter, int* doneIters);

    /// Finalizes and returns the results of a sliced path query.
    ///  @param[out]    path        An ordered list of polygon references representing the path. (Start to end.) 
    ///                              [(polyRef) * @p pathCount]
    ///  @param[out]    pathCount    The number of polygons returned in the @p path array.
    ///  @param[in]        maxPath        The max number of polygons the path array can hold. [Limit: >= 1]
    /// @returns The status flags for the query.
    dtStatus finalizeSlicedFindPath(dtPolyRef* path, int* pathCount, const int maxPath);
    
    /// Finalizes and returns the results of an incomplete sliced path query, returning the path to the furthest
    /// polygon on the existing path that was visited during the search.
    ///  @param[in]        existing        An array of polygon references for the existing path.
    ///  @param[in]        existingSize    The number of polygon in the @p existing array.
    ///  @param[out]    path            An ordered list of polygon references representing the path. (Start to end.) 
    ///                                  [(polyRef) * @p pathCount]
    ///  @param[out]    pathCount        The number of polygons returned in the @p path array.
    ///  @param[in]        maxPath            The max number of polygons the @p path array can hold. [Limit: >= 1]
    /// @returns The status flags for the query.
    dtStatus finalizeSlicedFindPathPartial(const dtPolyRef* existing, const int existingSize,
                                           dtPolyRef* path, int* pathCount, const int maxPath);

    ///@}
    /// @name Dijkstra Search Functions
    /// @{ 

    /// Finds the polygons along the navigation graph that touch the specified circle.
    ///  @param[in]        startRef        The reference id of the polygon where the search starts.
    ///  @param[in]        centerPos        The center of the search circle. [(x, y, z)]
    ///  @param[in]        radius            The radius of the search circle.
    ///  @param[in]        filter            The polygon filter to apply to the query.
    ///  @param[out]    resultRef        The reference ids of the polygons touched by the circle. [opt]
    ///  @param[out]    resultParent    The reference ids of the parent polygons for each result. 
    ///                                  Zero if a result polygon has no parent. [opt]
    ///  @param[out]    resultCost        The search cost from @p centerPos to the polygon. [opt]
    ///  @param[out]    resultCount        The number of polygons found. [opt]
    ///  @param[in]        maxResult        The maximum number of polygons the result arrays can hold.
    /// @returns The status flags for the query.
    dtStatus findPolysAroundCircle(dtPolyRef startRef, const float* centerPos, const float radius,
                                   const dtQueryFilter* filter,
                                   dtPolyRef* resultRef, dtPolyRef* resultParent, float* resultCost,
                                   int* resultCount, const int maxResult) const;
    
    /// Finds the polygons along the naviation graph that touch the specified convex polygon.
    ///  @param[in]        startRef        The reference id of the polygon where the search starts.
    ///  @param[in]        verts            The vertices describing the convex polygon. (CCW) 
    ///                                  [(x, y, z) * @p nverts]
    ///  @param[in]        nverts            The number of vertices in the polygon.
    ///  @param[in]        filter            The polygon filter to apply to the query.
    ///  @param[out]    resultRef        The reference ids of the polygons touched by the search polygon. [opt]
    ///  @param[out]    resultParent    The reference ids of the parent polygons for each result. Zero if a 
    ///                                  result polygon has no parent. [opt]
    ///  @param[out]    resultCost        The search cost from the centroid point to the polygon. [opt]
    ///  @param[out]    resultCount        The number of polygons found.
    ///  @param[in]        maxResult        The maximum number of polygons the result arrays can hold.
    /// @returns The status flags for the query.
    dtStatus findPolysAroundShape(dtPolyRef startRef, const float* verts, const int nverts,
                                  const dtQueryFilter* filter,
                                  dtPolyRef* resultRef, dtPolyRef* resultParent, float* resultCost,
                                  int* resultCount, const int maxResult) const;
    
    /// @}
    /// @name Local Query Functions
    ///@{

    /// Finds the polygon nearest to the specified center point.
    ///  @param[in]        center        The center of the search box. [(x, y, z)]
    ///  @param[in]        extents        The search distance along each axis. [(x, y, z)]
    ///  @param[in]        filter        The polygon filter to apply to the query.
    ///  @param[out]    nearestRef    The reference id of the nearest polygon.
    ///  @param[out]    nearestPt    The nearest point on the polygon. [opt] [(x, y, z)]
    /// @returns The status flags for the query.
    dtStatus findNearestPoly(const float* center, const float* extents,
                             const dtQueryFilter* filter,
                             dtPolyRef* nearestRef, float* nearestPt) const;
    
    /// Finds polygons that overlap the search box.
    ///  @param[in]        center        The center of the search box. [(x, y, z)]
    ///  @param[in]        extents        The search distance along each axis. [(x, y, z)]
    ///  @param[in]        filter        The polygon filter to apply to the query.
    ///  @param[out]    polys        The reference ids of the polygons that overlap the query box.
    ///  @param[out]    polyCount    The number of polygons in the search result.
    ///  @param[in]        maxPolys    The maximum number of polygons the search result can hold.
    /// @returns The status flags for the query.
    dtStatus queryPolygons(const float* center, const float* extents,
                           const dtQueryFilter* filter,
                           dtPolyRef* polys, int* polyCount, const int maxPolys) const;

    /// Finds the non-overlapping navigation polygons in the local neighbourhood around the center position.
    ///  @param[in]        startRef        The reference id of the polygon where the search starts.
    ///  @param[in]        centerPos        The center of the query circle. [(x, y, z)]
    ///  @param[in]        radius            The radius of the query circle.
    ///  @param[in]        filter            The polygon filter to apply to the query.
    ///  @param[out]    resultRef        The reference ids of the polygons touched by the circle.
    ///  @param[out]    resultParent    The reference ids of the parent polygons for each result. 
    ///                                  Zero if a result polygon has no parent. [opt]
    ///  @param[out]    resultCount        The number of polygons found.
    ///  @param[in]        maxResult        The maximum number of polygons the result arrays can hold.
    /// @returns The status flags for the query.
    dtStatus findLocalNeighbourhood(dtPolyRef startRef, const float* centerPos, const float radius,
                                    const dtQueryFilter* filter,
                                    dtPolyRef* resultRef, dtPolyRef* resultParent,
                                    int* resultCount, const int maxResult) const;

    /// Moves from the start to the end position constrained to the navigation mesh.
    ///  @param[in]        startRef        The reference id of the start polygon.
    ///  @param[in]        startPos        A position of the mover within the start polygon. [(x, y, x)]
    ///  @param[in]        endPos            The desired end position of the mover. [(x, y, z)]
    ///  @param[in]        filter            The polygon filter to apply to the query.
    ///  @param[out]    resultPos        The result position of the mover. [(x, y, z)]
    ///  @param[out]    visited            The reference ids of the polygons visited during the move.
    ///  @param[out]    visitedCount    The number of polygons visited during the move.
    ///  @param[in]        maxVisitedSize    The maximum number of polygons the @p visited array can hold.
    /// @returns The status flags for the query.
    dtStatus moveAlongSurface(dtPolyRef startRef, const float* startPos, const float* endPos,
                              const dtQueryFilter* filter,
                              float* resultPos, dtPolyRef* visited, int* visitedCount, const int maxVisitedSize) const;
    
    /// Casts a 'walkability' ray along the surface of the navigation mesh from 
    /// the start position toward the end position.
    /// @note A wrapper around raycast(..., RaycastHit*). Retained for backward compatibility.
    ///  @param[in]        startRef    The reference id of the start polygon.
    ///  @param[in]        startPos    A position within the start polygon representing 
    ///                              the start of the ray. [(x, y, z)]
    ///  @param[in]        endPos        The position to cast the ray toward. [(x, y, z)]
    ///  @param[out]    t            The hit parameter. (FLT_MAX if no wall hit.)
    ///  @param[out]    hitNormal    The normal of the nearest wall hit. [(x, y, z)]
    ///  @param[in]        filter        The polygon filter to apply to the query.
    ///  @param[out]    path        The reference ids of the visited polygons. [opt]
    ///  @param[out]    pathCount    The number of visited polygons. [opt]
    ///  @param[in]        maxPath        The maximum number of polygons the @p path array can hold.
    /// @returns The status flags for the query.
    dtStatus raycast(dtPolyRef startRef, const float* startPos, const float* endPos,
                     const dtQueryFilter* filter,
                     float* t, float* hitNormal, dtPolyRef* path, int* pathCount, const int maxPath) const;
    
    /// Casts a 'walkability' ray along the surface of the navigation mesh from 
    /// the start position toward the end position.
    ///  @param[in]        startRef    The reference id of the start polygon.
    ///  @param[in]        startPos    A position within the start polygon representing 
    ///                              the start of the ray. [(x, y, z)]
    ///  @param[in]        endPos        The position to cast the ray toward. [(x, y, z)]
    ///  @param[in]        filter        The polygon filter to apply to the query.
    ///  @param[in]        flags        govern how the raycast behaves. See dtRaycastOptions
    ///  @param[out]    hit            Pointer to a raycast hit structure which will be filled by the results.
    ///  @param[in]        prevRef        parent of start ref. Used during for cost calculation [opt]
    /// @returns The status flags for the query.
    dtStatus raycast(dtPolyRef startRef, const float* startPos, const float* endPos,
                     const dtQueryFilter* filter, const unsigned int options,
                     dtRaycastHit* hit, dtPolyRef prevRef = 0) const;


    /// Finds the distance from the specified position to the nearest polygon wall.
    ///  @param[in]        startRef        The reference id of the polygon containing @p centerPos.
    ///  @param[in]        centerPos        The center of the search circle. [(x, y, z)]
    ///  @param[in]        maxRadius        The radius of the search circle.
    ///  @param[in]        filter            The polygon filter to apply to the query.
    ///  @param[out]    hitDist            The distance to the nearest wall from @p centerPos.
    ///  @param[out]    hitPos            The nearest position on the wall that was hit. [(x, y, z)]
    ///  @param[out]    hitNormal        The normalized ray formed from the wall point to the 
    ///                                  source point. [(x, y, z)]
    /// @returns The status flags for the query.
    dtStatus findDistanceToWall(dtPolyRef startRef, const float* centerPos, const float maxRadius,
                                const dtQueryFilter* filter,
                                float* hitDist, float* hitPos, float* hitNormal) const;
    
    /// Returns the segments for the specified polygon, optionally including portals.
    ///  @param[in]        ref                The reference id of the polygon.
    ///  @param[in]        filter            The polygon filter to apply to the query.
    ///  @param[out]    segmentVerts    The segments. [(ax, ay, az, bx, by, bz) * segmentCount]
    ///  @param[out]    segmentRefs        The reference ids of each segment's neighbor polygon. 
    ///                                  Or zero if the segment is a wall. [opt] [(parentRef) * @p segmentCount] 
    ///  @param[out]    segmentCount    The number of segments returned.
    ///  @param[in]        maxSegments        The maximum number of segments the result arrays can hold.
    /// @returns The status flags for the query.
    dtStatus getPolyWallSegments(dtPolyRef ref, const dtQueryFilter* filter,
                                 float* segmentVerts, dtPolyRef* segmentRefs, int* segmentCount,
                                 const int maxSegments) const;

    /// Returns random location on navmesh.
    /// Polygons are chosen weighted by area. The search runs in linear related to number of polygon.
    ///  @param[in]        filter            The polygon filter to apply to the query.
    ///  @param[in]        frand            Function returning a random number [0..1).
    ///  @param[out]    randomRef        The reference id of the random location.
    ///  @param[out]    randomPt        The random location. 
    /// @returns The status flags for the query.
    dtStatus findRandomPoint(const dtQueryFilter* filter, float (*frand)(),
                             dtPolyRef* randomRef, float* randomPt) const;

    /// Returns random location on navmesh within the reach of specified location.
    /// Polygons are chosen weighted by area. The search runs in linear related to number of polygon.
    /// The location is not exactly constrained by the circle, but it limits the visited polygons.
    ///  @param[in]        startRef        The reference id of the polygon where the search starts.
    ///  @param[in]        centerPos        The center of the search circle. [(x, y, z)]
    ///  @param[in]        filter            The polygon filter to apply to the query.
    ///  @param[in]        frand            Function returning a random number [0..1).
    ///  @param[out]    randomRef        The reference id of the random location.
    ///  @param[out]    randomPt        The random location. [(x, y, z)]
    /// @returns The status flags for the query.
    dtStatus findRandomPointAroundCircle(dtPolyRef startRef, const float* centerPos, const float maxRadius,
                                         const dtQueryFilter* filter, float (*frand)(),
                                         dtPolyRef* randomRef, float* randomPt) const;
    
    /// Finds the closest point on the specified polygon.
    ///  @param[in]        ref            The reference id of the polygon.
    ///  @param[in]        pos            The position to check. [(x, y, z)]
    ///  @param[out]    closest        The closest point on the polygon. [(x, y, z)]
    ///  @param[out]    posOverPoly    True of the position is over the polygon.
    /// @returns The status flags for the query.
    dtStatus closestPointOnPoly(dtPolyRef ref, const float* pos, float* closest, bool* posOverPoly) const;
    
    /// Returns a point on the boundary closest to the source point if the source point is outside the 
    /// polygon's xz-bounds.
    ///  @param[in]        ref            The reference id to the polygon.
    ///  @param[in]        pos            The position to check. [(x, y, z)]
    ///  @param[out]    closest        The closest point. [(x, y, z)]
    /// @returns The status flags for the query.
    dtStatus closestPointOnPolyBoundary(dtPolyRef ref, const float* pos, float* closest) const;
    
    /// Gets the height of the polygon at the provided position using the height detail. (Most accurate.)
    ///  @param[in]        ref            The reference id of the polygon.
    ///  @param[in]        pos            A position within the xz-bounds of the polygon. [(x, y, z)]
    ///  @param[out]    height        The height at the surface of the polygon.
    /// @returns The status flags for the query.
    dtStatus getPolyHeight(dtPolyRef ref, const float* pos, float* height) const;

    /// @}
    /// @name Miscellaneous Functions
    /// @{

    /// Returns true if the polygon reference is valid and passes the filter restrictions.
    ///  @param[in]        ref            The polygon reference to check.
    ///  @param[in]        filter        The filter to apply.
    bool isValidPolyRef(dtPolyRef ref, const dtQueryFilter* filter) const;

    /// Returns true if the polygon reference is in the closed list. 
    ///  @param[in]        ref        The reference id of the polygon to check.
    /// @returns True if the polygon is in closed list.
    bool isInClosedList(dtPolyRef ref) const;
    
    /// Gets the node pool.
    /// @returns The node pool.
    class dtNodePool* getNodePool() const { return m_nodePool; }
    
    /// Gets the navigation mesh the query object is using.
    /// @return The navigation mesh the query object is using.
    const dtNavMesh* getAttachedNavMesh() const { return m_nav; }

    /// @}
    
private:
    
    /// Returns neighbour tile based on side.
    dtMeshTile* getNeighbourTileAt(int x, int y, int side) const;

    /// Queries polygons within a tile.
    int queryPolygonsInTile(const dtMeshTile* tile, const float* qmin, const float* qmax, const dtQueryFilter* filter,
                            dtPolyRef* polys, const int maxPolys) const;

    /// Returns portal points between two polygons.
    dtStatus getPortalPoints(dtPolyRef from, dtPolyRef to, float* left, float* right,
                             unsigned char& fromType, unsigned char& toType) const;
    dtStatus getPortalPoints(dtPolyRef from, const dtPoly* fromPoly, const dtMeshTile* fromTile,
                             dtPolyRef to, const dtPoly* toPoly, const dtMeshTile* toTile,
                             float* left, float* right) const;
    
    /// Returns edge mid point between two polygons.
    dtStatus getEdgeMidPoint(dtPolyRef from, dtPolyRef to, float* mid) const;
    dtStatus getEdgeMidPoint(dtPolyRef from, const dtPoly* fromPoly, const dtMeshTile* fromTile,
                             dtPolyRef to, const dtPoly* toPoly, const dtMeshTile* toTile,
                             float* mid) const;
    
    // Appends vertex to a straight path
    dtStatus appendVertex(const float* pos, const unsigned char flags, const dtPolyRef ref,
                          float* straightPath, unsigned char* straightPathFlags, dtPolyRef* straightPathRefs,
                          int* straightPathCount, const int maxStraightPath) const;

    // Appends intermediate portal points to a straight path.
    dtStatus appendPortals(const int startIdx, const int endIdx, const float* endPos, const dtPolyRef* path,
                           float* straightPath, unsigned char* straightPathFlags, dtPolyRef* straightPathRefs,
                           int* straightPathCount, const int maxStraightPath, const int options) const;
    
    const dtNavMesh* m_nav;                ///< Pointer to navmesh data.

    struct dtQueryData
    {
        dtStatus status;
        struct dtNode* lastBestNode;
        float lastBestNodeCost;
        dtPolyRef startRef, endRef;
        float startPos[3], endPos[3];
        const dtQueryFilter* filter;
        unsigned int options;
        float raycastLimitSqr;
    };
    dtQueryData m_query;                ///< Sliced query state.

    class dtNodePool* m_tinyNodePool;    ///< Pointer to small node pool.
    class dtNodePool* m_nodePool;        ///< Pointer to node pool.
    class dtNodeQueue* m_openList;        ///< Pointer to open list queue.
};

/// Allocates a query object using the Detour allocator.
/// @return An allocated query object, or null on failure.
/// @ingroup detour
dtNavMeshQuery* dtAllocNavMeshQuery();

/// Frees the specified query object using the Detour allocator.
///  @param[in]        query        A query object allocated using #dtAllocNavMeshQuery
/// @ingroup detour
void dtFreeNavMeshQuery(dtNavMeshQuery* query);

#endif // DETOURNAVMESHQUERY_H
